package j2024.j202408;

import java.util.PriorityQueue;

public class j0812 {
    /**
     * 91. 解码方法
     * @param s
     * @return
     */
    public int numDecodings(String s) {
        int n = s.length();
        char[] str = s.toCharArray();
        int[] dp = new int[n];
        if(str[0]!='0'){
            dp[0]++;
        }
        if(s.length()==1){
            return dp[0];
        }
        if(str[0]!='0'  && str[1]!='0'){
            dp[1]++;
        }
        int t = (str[0]-'0')*10 + (str[1]-'0');
        if(t>=10 && t<=26){
            dp[1]++;
        }
        for (int i = 2; i < n; i++) {
            if(str[i]!='0'){
                dp[i]+=dp[i-1];
            }
            int tmp = (str[i-1]-'0')*10 + (str[i]-'0');
            if(tmp>=10 && tmp<=26){
                dp[i]+=dp[i-2];
            }
        }
        return dp[n-1];
    }
    public int numDecodings2(String s) {
        int n = s.length();
        char[] str = s.toCharArray();
        int[] dp = new int[n+1];
        dp[0] = 1;//保证后续填表正确
        if(str[0]!='0'){
            dp[1]++;
        }

        for (int i = 2; i <= n; i++) {
            if(str[i-1]!='0'){
                dp[i]+=dp[i-1];
            }
            int tmp = (str[i-2]-'0')*10 + (str[i-1]-'0');
            if(tmp>=10 && tmp<=26){
                dp[i]+=dp[i-2];
            }
        }
        return dp[n];
    }

    /**
     * 2208. 将数组和减半的最少操作次数
     * @param nums
     * @return
     */
    public int halveArray(int[] nums) {
        double sum = 0;
        PriorityQueue<Double> queue = new PriorityQueue<>((a,b)->b.compareTo(a));
        for (int i = 0; i < nums.length; i++) {
            sum+=nums[i];
            queue.offer((double)nums[i]);
        }
        double half = sum/2;
        int count = 0;
        while(sum>half){
            double tmp = queue.poll()/2;
            sum-=tmp;
            queue.offer(tmp);
            count++;
        }
        return count;
    }
}
